Publications HAL du projet ANR. STINT

2021

Journal articles

titre
Single‐conflict colouring
auteur
Zdeněk Dvořák, Louis Esperet, Ross J. Kang, Kenta Ozeki
article
Journal of Graph Theory, 2021, 97 (1), pp.148-160. ⟨10.1002/jgt.22646⟩
Accès au bibtex
https://arxiv.org/pdf/1803.10962 BibTex

2020

Journal articles

titre
Study of a Combinatorial Game in Graphs Through Linear Programming
auteur
Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes
article
Algorithmica, 2020, 82 (2), pp.212-244. ⟨10.1007/s00453-018-0503-9⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01881473/file/spygame_trees_grids_July18.pdf BibTex

2019

Journal articles

titre
Bipartite spanning sub(di)graphs induced by 2-partitions
auteur
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo
article
Journal of Graph Theory, 2019, 92 (2), pp.130-151. ⟨10.1002/jgt.22444⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02350210/file/Bipartite-revise.pdf BibTex
titre
A proof of the Erdős–Sands–Sauer–Woodrow conjecture
auteur
Nicolas Bousquet, William Lochet, Stéphan Thomassé
article
Journal of Combinatorial Theory, Series B, 2019, Elsevier Journal of Combinatorial Theory, Series B, 137, pp.316-319. ⟨10.1016/j.jctb.2018.11.005⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02158330/file/monoPath.pdf BibTex
titre
Improper coloring of graphs on surfaces
auteur
Ilkyoo Choi, Louis Esperet
article
Journal of Graph Theory, 2019, 91 (1), pp.16-34. ⟨10.1002/jgt.22418⟩
Accès au bibtex
https://arxiv.org/pdf/1603.02841 BibTex
titre
Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
auteur
Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé
article
Combinatorica, 2019, 39 (2), pp.239-263. ⟨10.1007/s00493-017-3661-5⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01744515/file/bt-paths5.pdf BibTex
titre
Distributed coloring in sparse graphs with fewer colors
auteur
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet
article
The Electronic Journal of Combinatorics, 2019, 26 (4), ⟨10.37236/8395⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02333202/file/1802.05582.pdf BibTex
titre
Separation Choosability and Dense Bipartite Induced Subgraphs
auteur
Louis Esperet, Ross Kang, Stéphan Thomassé
article
Combinatorics, Probability and Computing, 2019, 28 (5), pp.720-732. ⟨10.1017/S0963548319000026⟩
Accès au bibtex
https://arxiv.org/pdf/1802.03727 BibTex
titre
On spectrum assignment in elastic optical tree-networks
auteur
Jean-Claude Bermond, Fatima Zahra Moataz
article
Discrete Applied Mathematics, 2019, 257, pp.40-52. ⟨10.1016/j.dam.2018.09.021⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01962617/file/elasticDAMpreprintsubmission.pdf BibTex
titre
Exact distance coloring in trees
auteur
Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan, Rémi de Joannis de Verclos
article
Combinatorics, Probability and Computing, 2019, 28 (2), pp.177-186. ⟨10.1017/S0963548318000378⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01525789/file/exact_distance.pdf BibTex

2018

Journal articles

titre
On locally irregular decompositions and the 1-2 Conjecture in digraphs
auteur
Olivier Baudon, Julien Bensmail, Jakub Przybyło, Mariusz Woźniak
article
Discrete Mathematics and Theoretical Computer Science, 2018, vol. 20 no. 2, ⟨10.23638/DMTCS-20-2-7⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01374427/file/12-oriented.pdf BibTex
titre
χ-bounded families of oriented graphs
auteur
Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, Frédéric Maffray, Jose Zamora
article
Journal of Graph Theory, 2018, 89 (3), pp.304 - 326. ⟨10.1002/jgt.22252⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01882395/file/Induced-digraphs-revised.pdf BibTex
titre
χ-bounds, operations, and chords
auteur
Nicolas Trotignon, Lan Anh Pham
article
Journal of Graph Theory, 2018, 88 (2), pp.312 - 336. ⟨10.1002/jgt.22214⟩
Accès au bibtex
BibTex
titre
On interval number in cycle convexity
auteur
Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, Karol Suchan
article
Discrete Mathematics and Theoretical Computer Science, 2018, Vol. 20 no. 1 (1), pp.1-28. ⟨10.23638/DMTCS-20-1-13⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01394201/file/DMTCS_final.pdf BibTex
titre
Spy-game on graphs: Complexity and simple topologies
auteur
Nathann Cohen, Nicolas Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, Rudini Sampaio
article
Theoretical Computer Science, 2018, 725, pp.1 - 15. ⟨10.1016/j.tcs.2017.11.015⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01782246/file/Spygames1.pdf BibTex
titre
Decomposition techniques applied to the Clique-Stable set separation problem
auteur
Nicolas Bousquet, Aurélie Lagoutte, Frédéric Maffray, Lucas Pastor
article
Discrete Mathematics, 2018, 341 (5), pp.1492 - 1501. ⟨10.1016/j.disc.2017.10.014⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01804017/file/1703.07106.pdf BibTex
titre
Subdivisions of oriented cycles in digraphs with large chromatic number
auteur
Nathann Cohen, Frédéric Havet, William Lochet, Nicolas Nisse
article
Journal of Graph Theory, 2018, 89 (4), pp.439-456. ⟨10.1002/jgt.22360⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01834779/file/bounded-chi-cycle.pdf BibTex
titre
Finding a subdivision of a prescribed digraph of order 4
auteur
Frédéric Havet, Ana Karolinna Maia de Oliviera, Bojan Mohar
article
Journal of Graph Theory, 2018, 87 (4), pp.536-560. ⟨10.1002/jgt.22174⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01711403/file/revised1_JGT.pdf BibTex
titre
Out-degree reducing partitions of digraphs
auteur
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo
article
Theoretical Computer Science, 2018, 719, pp.64-72. ⟨10.1016/j.tcs.2017.11.007⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01765642/file/Maxreduce2part-revised.pdf BibTex
titre
Orienting edges to fight fire in graphs
auteur
Julien Bensmail, Nick Brettell
article
The Australasian Journal of Combinatorics, 2018, 71 (1), pp.12-42
Accès au texte intégral et bibtex
https://hal.science/hal-01166577/file/firefight.pdf BibTex
titre
On distance-preserving elimination orderings in graphs: Complexity and algorithms
auteur
David Coudert, Guillaume Ducoffe, Nicolas Nisse, Mauricio Soto
article
Discrete Applied Mathematics, 2018, 243, pp.140-153. ⟨10.1016/j.dam.2018.02.007⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01741277/file/dpo-hal.pdf BibTex
titre
Stable Sets in {ISK4,wheel}-Free Graphs
auteur
Martin Milanič, Irena Penev, Nicolas Trotignon
article
Algorithmica, 2018, 80 (2), pp.415 - 447. ⟨10.1007/s00453-016-0255-3⟩
Accès au bibtex
https://arxiv.org/pdf/1602.02916 BibTex
titre
Revisiting Decomposition by Clique Separators
auteur
David Coudert, Guillaume Ducoffe
article
SIAM Journal on Discrete Mathematics, 2018, 32 (1), pp.682 - 694. ⟨10.1137/16M1059837⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01753324/file/decomposition_by_clique_separators.pdf BibTex
titre
Packing and covering odd cycles in cubic plane graphs with small faces
auteur
Diego Nicodemos, Matej Stehlik
article
European Journal of Combinatorics, 2018, 67, pp.208 - 221. ⟨10.1016/j.ejc.2017.08.004⟩
Accès au bibtex
https://arxiv.org/pdf/1701.07748 BibTex
titre
A coloring algorithm for 4K1-free line graphs
auteur
Dallas Fraser, Angèle M. Hamel, Chinh T. Hoàng, Frédéric Maffray
article
Discrete Applied Mathematics, 2018, 234, pp.76 - 85. ⟨10.1016/j.dam.2017.06.006⟩
Accès au bibtex
BibTex
titre
On the Complexity of Compressing Two Dimensional Routing Tables with Order
auteur
Frédéric Giroire, Frédéric Havet, Joanna Moulierac
article
Algorithmica, 2018, 80 (1), pp.209 - 233. ⟨10.1007/s00453-016-0243-7⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01686641/file/compacting.pdf BibTex
titre
Extension from Precoloured Sets of Edges
auteur
Katherine Edwards, António Girão, Jan van den Heuvel, Ross J. Kang, Gregory J. Puleo, Jean-Sébastien Sereni
article
The Electronic Journal of Combinatorics, 2018, ⟨10.37236/6303⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01024843/file/EHK%2B18.pdf BibTex
titre
On the minimum size of an identifying code over all orientations of a graph
auteur
Nathann Cohen, Frédéric Havet
article
The Electronic Journal of Combinatorics, 2018, 25 (1), pp.#P1.49
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01765643/file/ejc-idor.pdf BibTex
titre
Recovery of disrupted airline operations using k-Maximum Matching in Graphs
auteur
Nicolas Nisse, Alexandre Salch, Valentin Weber
article
European Journal of Operational Research, 2018
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03583581/file/kmatching.pdf BibTex
titre
The width of quadrangulations of the projective plane
auteur
Louis Esperet, Matěj Stehlík
article
Journal of Graph Theory, 2018, 89 (1), pp.76-88. ⟨10.1002/jgt.22241⟩
Accès au bibtex
https://arxiv.org/pdf/1509.07716 BibTex
titre
Additive bases and flows in graphs
auteur
Louis Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, Stéphan Thomassé
article
SIAM Journal on Discrete Mathematics, 2018, 32 (1), pp.534-542. ⟨10.1137/17M1113758⟩
Accès au bibtex
https://arxiv.org/pdf/1701.03366 BibTex
titre
Polynomial expansion and sublinear separators
auteur
Louis Esperet, Jean-Florent Raymond
article
European Journal of Combinatorics, 2018, 69, pp.49-53. ⟨10.1016/j.ejc.2017.09.003⟩
Accès au bibtex
https://arxiv.org/pdf/1705.01438 BibTex

Conference papers

titre
Distributed coloring in sparse graphs with fewer colors
auteur
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet
article
ACM Symposium on Principles of Distributed Computing (PODC 2018), Jul 2018, Egham, United Kingdom. pp.419-425, ⟨10.1145/3212734.3212740⟩
Accès au bibtex
https://arxiv.org/pdf/1802.05582 BibTex
titre
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
auteur
David Coudert, Guillaume Ducoffe, Alexandru Popa
article
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. pp.20, ⟨10.1137/1.9781611975031.176⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01676187/file/P-FPT-2018.pdf BibTex

2017

Journal articles

titre
Bispindle in strongly connected digraphs with large chromatic number
auteur
Nathann Cohen, Frédéric Havet, William Lochet, Raul Lopes
article
Electronic Notes in Discrete Mathematics, 2017, 62, pp.69 - 74. ⟨10.1016/j.endm.2017.10.013⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01634307/file/template.pdf BibTex
titre
Flows and bisections in cubic graphs
auteur
Louis Esperet, Giuseppe Mazzuoccolo, Michael Tarsi
article
Journal of Graph Theory, 2017, 86 (2), pp.149-158. ⟨10.1002/jgt.22118⟩
Accès au bibtex
https://arxiv.org/pdf/1504.03500 BibTex
titre
On a directed variation of the 1-2-3 and 1-2 Conjectures
auteur
Emma Barme, Julien Bensmail, Jakub Przybyło, Mariusz Woźniak
article
Discrete Applied Mathematics, 2017, 217 (2), pp.123-131
Accès au texte intégral et bibtex
https://hal.science/hal-01175756/file/luczak-v2.pdf BibTex
titre
Colouring perfect graphs with bounded clique number
auteur
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour, Sophie Spirkl
article
Journal of Combinatorial Theory, Series B, 2017, 122, pp.757-775. ⟨10.1016/j.jctb.2016.09.006⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01561528/file/paper.pdf BibTex
titre
Coloring Jordan regions and curves
auteur
Wouter Cames van Batenburg, Louis Esperet, Tobias Müller
article
SIAM Journal on Discrete Mathematics, 2017, 31 (3), pp.1670-1684. ⟨10.1137/16M1092726⟩
Accès au bibtex
https://arxiv.org/pdf/1608.08159 BibTex
titre
A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
auteur
Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković
article
Algorithmica, 2017, 77 (3), pp.619 - 641. ⟨10.1007/s00453-015-0083-x⟩
Accès au bibtex
https://arxiv.org/pdf/1310.6205 BibTex
titre
On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph
auteur
Nicolas Trotignon, Kristina Vušković
article
Journal of Graph Theory, 2017, 84 (3), pp.233 - 248. ⟨10.1002/jgt.22023⟩
Accès au bibtex
https://arxiv.org/pdf/1407.6531 BibTex
titre
Applying clique-decomposition for computing Gromov hyperbolicity
auteur
Nathann Cohen, David Coudert, Guillaume Ducoffe, Aurélien Lancin
article
Theoretical Computer Science, 2017, 690, pp.114-139. ⟨10.1016/j.tcs.2017.06.001⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01540756/file/CCDL-2017.pdf BibTex
titre
On rank-width of even-hole-free graphs
auteur
Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
article
Discrete Mathematics and Theoretical Computer Science, 2017, 19 (1)
Accès au bibtex
BibTex
titre
Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs
auteur
Martin Milanič, Nicolas Trotignon
article
Journal of Graph Theory, 2017, 84 (3), pp.536 - 551. ⟨10.1002/jgt.22040⟩
Accès au bibtex
BibTex
titre
Exclusive graph searching vs. pathwidth
auteur
Euripides Markou, Nicolas Nisse, Stéphane Pérennes
article
Information and Computation, 2017, 252, pp.243 - 260. ⟨10.1016/j.ic.2016.11.007⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01534596/file/journal_revised.pdf BibTex
titre
Long induced paths in graphs
auteur
Louis Esperet, Laetitia Lemoine, Frédéric Maffray
article
European Journal of Combinatorics, 2017, 62, pp.1-14. ⟨10.1016/j.ejc.2016.11.011⟩
Accès au bibtex
https://arxiv.org/pdf/1602.06836 BibTex
titre
Small feedback vertex sets in planar digraphs
auteur
Louis Esperet, Laetitia Lemoine, Frédéric Maffray
article
The Electronic Journal of Combinatorics, 2017, 24 (2), pp.P2.6. ⟨10.37236/6252⟩
Accès au bibtex
https://arxiv.org/pdf/1606.04419 BibTex
titre
Fullerene graphs of small diameter
auteur
Diego Nicodemos, Matej Stehlik
article
MATCH Communications in Mathematical and in Computer Chemistry, 2017, 77, pp.725-728
Accès au bibtex
https://arxiv.org/pdf/1604.01934 BibTex
titre
On color-critical (P5,co-P5)-free graphs
auteur
Harjinder S. Dhaliwal, Angele M Hamel, Chinh T. Hoàng, Frédéric Maffray, Tyler J.D. Mcconnell, Stefan A. Panait
article
Discrete Applied Mathematics, 2017, 216, pp.142-148. ⟨10.1016/j.dam.2016.05.018⟩
Accès au bibtex
BibTex
titre
Equitable Colorings of $K_4$-minor-free Graphs
auteur
Rémi de Joannis de Verclos, Jean-Sébastien Sereni
article
Journal of Graph Algorithms and Applications, 2017, 21 (6), pp.1091 - 1105. ⟨10.7155/jgaa.00451⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01483972/file/dJSe16.pdf BibTex
titre
Box representations of embedded graphs
auteur
Louis Esperet
article
Discrete and Computational Geometry, 2017, 57 (3), pp.590-606. ⟨10.1007/s00454-016-9837-8⟩
Accès au bibtex
https://arxiv.org/pdf/1512.02381 BibTex
titre
Colouring graphs with constraints on connectivity
auteur
Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon
article
Journal of Graph Theory, 2017, 85 (4), pp.814-838. ⟨10.1002/jgt.22109⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01570035/file/colourConnectivity.pdf BibTex
titre
Identifying codes for infinite triangular grids with a finite number of rows
auteur
Rennan Dantas, Frédéric Havet, Rudini M Sampaio
article
Discrete Mathematics, 2017, 340, pp.1584 - 1597. ⟨10.1016/j.disc.2017.02.015⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01527023/file/tri-rudini.pdf BibTex
titre
Maximum weight independent sets in classes related to claw-free graphs
auteur
T. Karthick, Frédéric Maffray
article
Discrete Applied Mathematics, 2017, 216, pp.233-239. ⟨10.1016/j.dam.2015.02.012⟩
Accès au bibtex
BibTex
titre
Graphs with No Induced Five-Vertex Path or Antipath
auteur
Maria Chudnovsky, Louis Esperet, Laetitia Lemoine, Peter Maceli, Frédéric Maffray, Irena Penev
article
Journal of Graph Theory, 2017, 84 (3), pp.221-232. ⟨10.1002/jgt.22022⟩
Accès au bibtex
https://arxiv.org/pdf/1410.0871 BibTex
titre
Coloring graphs with no even hole ≥ 6: the triangle-free case
auteur
Aurélie Lagoutte
article
The Electronic Journal of Combinatorics, 2017, 24 (3), pp.#P3.8. ⟨10.37236/5351⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01566608/file/YesC4_version_publiee.pdf BibTex

Conference papers

titre
Recovery of disrupted airline operations using k-Maximum Matching in graphs
auteur
Julien Bensmail, Valentin Garnero, Nicolas Nisse, Alexandre Salch, Valentin Weber
article
IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Sep 2017, Marseille, France. pp.3-8
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01534598/file/LAGOS17.pdf BibTex
titre
Gossiping with interference in radio ring networks
auteur
Jean-Claude Bermond, Takako Kodate, Joseph Yu
article
20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Aug 2017, TOKYO, Japan
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01963492/file/abstract-final2017%20.pdf BibTex
titre
A simple approach for lower-bounding the distortion in any Hyperbolic embedding
auteur
David Coudert, Guillaume Ducoffe
article
EUROCOMB'17 -- The European Conference on Combinatorics, Graph Theory and Applications, Aug 2017, Vienna, Austria. pp.293 - 299, ⟨10.1016/j.endm.2017.06.051⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01573042/file/CouDuc--EUROCOMB17.pdf BibTex
titre
Complexity Dichotomies for the Minimum $F$-Overlay Problem
auteur
Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant
article
28th International Workshop on Combinatorial Algorithms (IWOCA), Jul 2017, Newcastle, Australia. pp.116-127, ⟨10.1007/978-3-319-78825-8_10⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01571229/file/iwoca2017-SUBMITTED.pdf BibTex
titre
Token Sliding on Chordal Graphs
auteur
Nicolas Bousquet, Marthe Bonamy
article
WG (Workshop on Graphs), Jun 2017, Heeze, Netherlands
Accès au bibtex
BibTex
titre
Computing maximum cliques in B 2 EPG graphs
auteur
Nicolas Bousquet, Marc Heinrich
article
WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands
Accès au texte intégral et bibtex
https://hal.science/hal-01557335/file/clique-bepg_arxiv.pdf BibTex
titre
Study of a combinatorial game in graphs through Linear Programming
auteur
Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes
article
28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017, Phuket, Thailand. ⟨10.4230/LIPIcs⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01582091/file/ISAAC2017_revised.pdf BibTex
titre
Additive bases and flows in graphs
auteur
Louis Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, Stéphan Thomassé
article
The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17), 2017, Vienne, Austria. pp.399-405, ⟨10.1016/j.endm.2017.06.066⟩
Accès au bibtex
https://arxiv.org/pdf/1701.03366 BibTex

2016

Journal articles

titre
Weighted independent sets in classes of P6-free graphs
auteur
T. Karthick, Frédéric Maffray
article
Discrete Applied Mathematics, 2016, 9th International Colloquium on Graph Theory and Combinatorics, 2014, Grenoble, 209, pp.217-226. ⟨10.1016/j.dam.2015.10.015⟩
Accès au bibtex
BibTex
titre
Combinatorial optimization in networks with Shared Risk Link Groups
auteur
David Coudert, Stéphane Pérennes, Hervé Rivano, Marie-Emilie Voge
article
Discrete Mathematics and Theoretical Computer Science, 2016, Vol. 18 no. 3 (3), pp.25. ⟨10.46298/dmtcs.1297⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01053859/file/dmtcs-1420.pdf BibTex
titre
Isolating Highly Connected Induced Subgraphs
auteur
Irena Penev, Stéphan Thomassé, Nicolas Trotignon
article
SIAM Journal on Discrete Mathematics, 2016, 30, pp.592-619. ⟨10.1137/140981939⟩
Accès au bibtex
BibTex
titre
The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem
auteur
Louis Esperet, Giuseppe Mazzuoccolo, Michael Tarsi
article
Journal of Combinatorics, 2016, 7 (2), pp.453-479. ⟨10.4310/JOC.2016.v7.n2.a12⟩
Accès au bibtex
https://arxiv.org/pdf/1501.03774 BibTex
titre
Well Balanced Designs for Data Placement
auteur
Jean-Claude Bermond, Alain Jean-Marie, Dorian Mazauric, Joseph Yu
article
Journal of Combinatorial Designs, 2016, 24 (2), pp.55-76. ⟨10.1002/jcd.21506⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01223288/file/revfinal.pdf BibTex
titre
Strong edge-coloring of $(3, \Delta)$-bipartite graphs
auteur
Julien Bensmail, Aurélie Lagoutte, Petru Valicov
article
Discrete Mathematics, 2016, 339 (1), ⟨10.1016/j.disc.2015.08.026⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01080279/file/paper_v2.pdf BibTex
titre
Perfect graphs of arbitrarily large clique-chromatic number
auteur
Pierre Charbit, Irena Penev, Stéphan Thomassé, Nicolas Trotignon
article
Journal of Combinatorial Theory, Series B, 2016, 116, pp.456-464. ⟨10.1016/j.jctb.2015.09.008⟩
Accès au bibtex
https://arxiv.org/pdf/1506.08628 BibTex
titre
Finding good 2-partitions of digraphs I. Hereditary properties
auteur
Jørgen Bang-Jensen, Frédéric Havet
article
Theoretical Computer Science, 2016, 636, pp.85-94. ⟨10.1016/j.tcs.2016.05.029⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01327015/file/D2partH.pdf BibTex
titre
Boxicity and topological invariants
auteur
Louis Esperet
article
European Journal of Combinatorics, 2016, 51, pp.495-499. ⟨10.1016/j.ejc.2015.07.020⟩
Accès au bibtex
https://arxiv.org/pdf/1503.05765 BibTex
titre
Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth and Directed Pathwidth
auteur
David Coudert, Dorian Mazauric, Nicolas Nisse
article
ACM Journal of Experimental Algorithmics, 2016, 21 (1), pp.23. ⟨10.1145/2851494⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01266496/file/babpw-20151120.pdf BibTex
titre
The complexity of finding arc-disjoint branching flows
auteur
Jørgen Bang-Jensen, Frédéric Havet, Anders Yeo
article
Discrete Applied Mathematics, 2016, 209, pp.16-26. ⟨10.1016/j.dam.2015.10.012⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01360910/file/bflows4.pdf BibTex
titre
On the Choosability of Claw-Free Perfect Graphs
auteur
Sylvain Gravier, Frédéric Maffray, Lucas Pastor
article
Graphs and Combinatorics, 2016, 32, pp.2393-2413. ⟨10.1007/s00373-016-1732-9⟩
Accès au bibtex
BibTex
titre
Equitable orientations of sparse uniform hypergraphs
auteur
Nathann Cohen, William Lochet
article
The Electronic Journal of Combinatorics, 2016, 23 (4), pp.4-31
Accès au texte intégral et bibtex
https://hal.science/hal-01417832/file/prod.pdf BibTex
titre
Data center interconnection networks are not hyperbolic
auteur
David Coudert, Guillaume Ducoffe
article
Theoretical Computer Science, 2016, 639, pp.72-90. ⟨10.1016/j.tcs.2016.05.025⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01323301/file/data-centers--and--hyperbolicity.pdf BibTex
titre
Vizing Bound for the Chromatic Number on Some Graph Classes
auteur
T. Karthick, Frédéric Maffray
article
Graphs and Combinatorics, 2016, 32 (4), pp.1447-1460. ⟨10.1007/s00373-015-1651-1⟩
Accès au bibtex
BibTex
titre
Restricted frame graphs and a conjecture of Scott
auteur
Jérémie Chalopin, Louis Esperet, Zhentao Li, Patrice Ossona de Mendez
article
The Electronic Journal of Combinatorics, 2016, 23 (1), pp.#P1.30. ⟨10.37236/4424⟩
Accès au bibtex
https://arxiv.org/pdf/1406.0338 BibTex
titre
The Maximum Weight Stable Set Problem in (P6, bull)-Free Graphs
auteur
Frédéric Maffray, Lucas Pastor
article
Lecture Notes in Computer Science, 2016, WG 2016, 9941, pp.85-96. ⟨10.1007/978-3-662-53536-3_8⟩
Accès au bibtex
BibTex
titre
Maximum Weight Independent Sets in (S1,1,3, bull)-free Graphs
auteur
T. Karthick, Frédéric Maffray
article
Lecture Notes in Computer Science, 2016, COCOON 2016, 9797, pp.385-392. ⟨10.1007/978-3-319-42634-1_31⟩
Accès au bibtex
BibTex
titre
Clique-Stable Set Separation in Perfect Graphs with no Balanced Skew-Partitions
auteur
Aurélie Lagoutte, Théophile Trunck
article
Discrete Mathematics, 2016, 339, pp.1809 - 1825. ⟨10.1016/j.disc.2016.02.005⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01508655/file/cliquestable_skew_elsarticle_revision_2.pdf BibTex
titre
To Approximate Treewidth, Use Treelength!
auteur
David Coudert, Guillaume Ducoffe, Nicolas Nisse
article
SIAM Journal on Discrete Mathematics, 2016, 30 (3), pp.13. ⟨10.1137/15M1034039⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01348965/file/treewidth-treelength.pdf BibTex
titre
On the hyperbolicity of bipartite graphs and intersection graphs
auteur
David Coudert, Guillaume Ducoffe
article
Discrete Applied Mathematics, 2016, 214, pp.187-195. ⟨10.1016/j.dam.2016.06.017⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01220132/file/bipartite.pdf BibTex
titre
Coloring non-crossing strings
auteur
Louis Esperet, Daniel Gonçalves, Arnaud Labourel
article
The Electronic Journal of Combinatorics, 2016, 23 (4), pp.4.4. ⟨10.37236/5710⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01480244/file/5710-18757-3-PB.pdf BibTex
titre
Proper orientation of cacti
auteur
Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva
article
Theoretical Computer Science, 2016, 639, pp.14-25. ⟨10.1016/j.tcs.2016.05.016⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01338646/file/proper-cacti-TCS-FINAL.pdf BibTex
titre
Islands in graphs on surfaces
auteur
Louis Esperet, Pascal Ochem
article
SIAM Journal on Discrete Mathematics, 2016, 30 (1), pp.206-219. ⟨10.1137/140957883⟩
Accès au bibtex
https://arxiv.org/pdf/1402.2475 BibTex

Conference papers

titre
Identifying codes for infinite triangular grids with a finite number of rows
auteur
Rennan Dantas, Frédéric Havet, Rudini M Sampaio
article
Bordeaux Graph Workshop 2016, Nov 2016, Bordeaux, France
Accès au texte intégral et bibtex
https://hal.science/hal-01411109/file/Triang-code-BGW.pdf BibTex
titre
Subdivisions of oriented cycles in digraphs with large chromatic number
auteur
Nathann Cohen, Frédéric Havet, William Lochet, Nicolas Nisse
article
Bordeaux Graph Wokshop 2016, Nov 2016, Bordeaux, France. pp.85-88
Accès au texte intégral et bibtex
https://hal.science/hal-01411115/file/finalversion.pdf BibTex
titre
The Parallel Complexity of Coloring Games
auteur
Guillaume Ducoffe
article
9th International Symposium, SAGT 2016, Sep 2016, Liverpool, United Kingdom. pp.27-39, ⟨10.1007/978-3-662-53354-3_3⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01361056/file/Duc-SAGT16-finale.pdf BibTex
titre
Bin Packing with Colocations
auteur
Jean-Claude Bermond, Nathann Cohen, David Coudert, Dimitrios Letsios, Ioannis Milis, Stéphane Pérennes, Vassilis Zissimopoulos
article
14th International Workshop on Approximation and Online Algorithms (WAOA), Aug 2016, Aarhus, Denmark. pp.40-51, ⟨10.1007/978-3-319-51741-4_4⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01435614/file/revjcb.pdf BibTex
titre
On the Complexity of Computing Treebreadth
auteur
Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse
article
27th International Workshop on Combinatorial Algorithms, IWOCA 2016, Aug 2016, Helsinki, Finland. pp.3-15, ⟨10.1007/978-3-319-44543-4_1⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01354996/file/DLN-IWOCA16.pdf BibTex
titre
Minimum-Density Identifying Codes in Square Grids
auteur
Marwane Bouznif, Frédéric Havet, Myriam Preissmann
article
11th International Conference, AAIM 2016, Riccardo Dondi, Jul 2016, Bergamo, Italy. pp.77-88, ⟨10.1007/978-3-319-41168-2_7⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01346750/file/AAIM-grid-code.pdf BibTex
titre
Spy-Game on graphs
auteur
Nathann Cohen, Mathieu Hilaire, Nicolas Martins, Nicolas Nisse, Stéphane Pérennes
article
8th International Conference on Fun with Algorithms, FUN 2016, 2016, La Maddalena, Maddalena Islands, Italy. ⟨10.4230/LIPIcs.FUN.2016.10⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01326446/file/SpyGame_FUN_revised.pdf BibTex

2015

Journal articles

titre
Robust Energy-aware Routing with Redundancy Elimination
auteur
David Coudert, Alvinice Kodjo, Truong Khoa Phan
article
Computers and Operations Research, 2015, 64, pp.21. ⟨10.1016/j.cor.2015.05.008⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01155639/file/CKP15.pdf BibTex
titre
Even pairs in square-free Berge graphs
auteur
Frédéric Maffray
article
Electronic Notes in Discrete Mathematics, 2015, The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, 49, pp.173-180. ⟨10.1016/j.endm.2015.06.026⟩
Accès au bibtex
https://arxiv.org/pdf/1502.03695 BibTex
titre
Wheel-free planar graphs
auteur
Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon
article
European Journal of Combinatorics, 2015, 49, ⟨10.1016/j.ejc.2015.02.027⟩
Accès au bibtex
https://arxiv.org/pdf/1309.7120 BibTex
titre
Colouring quadrangulations of projective spaces
auteur
Tomas Kaiser, Matej Stehlik
article
Journal of Combinatorial Theory, Series B, 2015, 113, pp.1 -17. ⟨10.1016/j.jctb.2014.12.007⟩
Accès au bibtex
https://arxiv.org/pdf/1310.5875 BibTex
titre
Connected Surveillance Game
auteur
Frédéric Giroire, Ioannis Lamprou, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, Ronan Soares
article
Theoretical Computer Science, 2015, 584, pp.131-143
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01163170/file/Connected-Surveillance-Journal%20-%20vHAL.pdf BibTex
titre
Non-deterministic graph searching in trees
auteur
Omid Amini, David Coudert, Nicolas Nisse
article
Theoretical Computer Science, 2015, 580, pp.101-121. ⟨10.1016/j.tcs.2015.02.038⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01132032/file/ACN15.pdf BibTex
titre
Finding disjoint paths in networks with star shared risk link groups
auteur
Jean-Claude Bermond, David Coudert, Gianlorenzo d'Angelo, Fatima Zahra Moataz
article
Theoretical Computer Science, 2015, 579, pp.74-87. ⟨10.1016/j.tcs.2015.02.012⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01132216/file/BCDM15.pdf BibTex
titre
Vertex elimination orderings for hereditary graph classes
auteur
Pierre Aboulker, Pierre Charbit, Nicolas Trotignon, Kristina Vušković
article
Discrete Mathematics, 2015, 338 (5), ⟨10.1016/j.disc.2014.12.014⟩
Accès au bibtex
https://arxiv.org/pdf/1205.2535 BibTex
titre
On the proper orientation number of bipartite graphs
auteur
Julio Araujo, Nathann Cohen, Susanna F. de Rezende, Frédéric Havet, Phablo Moura
article
Theoretical Computer Science, 2015, 566, pp.59-75. ⟨10.1016/j.tcs.2014.11.037⟩
Accès au bibtex
BibTex
titre
Equitable partition of graphs into induced forests
auteur
Louis Esperet, Laetitia Lemoine, Frédéric Maffray
article
Discrete Mathematics, 2015, 338 (8), pp.1481-1483. ⟨10.1016/j.disc.2015.03.019⟩
Accès au bibtex
https://arxiv.org/pdf/1410.0861 BibTex
titre
Coloring perfect graphs with no balanced skew-partitions
auteur
Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck, Kristina Vušković
article
Journal of Combinatorial Theory, Series B, 2015, 115, pp.26-65. ⟨10.1016/j.jctb.2015.04.007⟩
Accès au bibtex
https://arxiv.org/pdf/1308.6444 BibTex
titre
Graphs with no induced wheel and no induced antiwheel
auteur
Frédéric Maffray
article
Applicable Analysis and Discrete Mathematics, 2015, 9, pp.357-366. ⟨10.2298/AADM150930020M⟩
Accès au bibtex
BibTex
titre
On computing the Gromov hyperbolicity
auteur
Nathann Cohen, David Coudert, Aurélien Lancin
article
ACM Journal of Experimental Algorithmics, 2015, 20 (1), pp.18. ⟨10.1145/2780652⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01182890/file/CCL15-no-format.pdf BibTex
titre
On the complexity of equal shortest path routing
auteur
Frédéric Giroire, Stéphane Pérennes, Issam Tahiri
article
Networks, 2015, ⟨10.1002/net.21612⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01218473/file/ospf-journal.pdf BibTex
titre
The Erdős–Hajnal conjecture for paths and antipaths
auteur
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
article
Journal of Combinatorial Theory, Series B, 2015, 113, pp.261-264. ⟨10.1016/j.jctb.2015.01.001⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01134469/file/pathantipath_elsarticle_revisee.pdf BibTex
titre
The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
auteur
S. Dantas, Celina de Figueiredo, Frédéric Maffray, Rafael B. Teixeira
article
Discrete Applied Mathematics, 2015, 182 (spec), pp.15-24. ⟨10.1016/j.dam.2013.09.004⟩
Accès au bibtex
BibTex
titre
Identifying codes in hereditary classes of graphs and VC-dimension
auteur
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, Stéphan Thomassé
article
SIAM Journal on Discrete Mathematics, 2015, 29 (4), pp.2047-2064. ⟨10.1137/14097879X⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01038012/file/Identifying_codes_and_VC-dimension_final_siam.pdf BibTex

Conference papers

titre
Study of Repair Protocols for Live Video Streaming Distributed Systems
auteur
Frédéric Giroire, Nicolas Huin
article
IEEE GLOBECOM 2015 - Global Communications Conference, Dec 2015, San Diego, United States
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01221319/file/gc15%20camera%20ready.pdf BibTex
titre
How to design graphs with low forwarding index and limited number of edges
auteur
Frédéric Giroire, Stéphane Pérennes, Issam Tahiri
article
26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Oct 2015, Verona, Italy
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01221650/file/iwoca15-camera-ready%20%281%29.pdf BibTex
titre
On Computing the Hyperbolicity of Real-World Graphs
auteur
Michele Borassi, David Coudert, Pierluigi Crescenzi, Andrea Marino
article
23rd Annual European Symposium on Algorithms (ESA), Sep 2015, Patras, Greece. pp.215-226, ⟨10.1007/978-3-662-48350-3_19⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01199860/file/BCCM15.pdf BibTex
titre
Finding Paths in Grids with Forbidden Transitions
auteur
Mamadou Moustapha Kanté, Fatima Zahra Moataz, Benjamin Momège, Nicolas Nisse
article
WG 2015, 41st International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2015, Munich, Germany
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01162796/file/PAFT_WGV0.pdf BibTex
titre
Minimum Size Tree-decompositions
auteur
Bi Li, Fatima Zahra Moataz, Nicolas Nisse, Karol Suchan
article
LAGOS 2015 – VIII Latin-American Algorithms, Graphs and Optimization Symposium, May 2015, Beberibe, Ceará, Brazil
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01162695/file/MSTD.pdf BibTex
titre
Grid spanners with low forwarding index for energy efficient networks
auteur
Frédéric Giroire, Stephane Perennes, Issam Tahiri
article
International Network Optimization Conference (INOC), May 2015, Warsaw, Poland
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01218411/file/camera-ready-inoc.pdf BibTex

2014

Journal articles

titre
Complexity of colouring problems restricted to unichord-free and { square,unichord }-free graphs
auteur
Raphael C.S. Machado, Celina M.H. de Figueiredo, Nicolas Trotignon
article
Discrete Applied Mathematics, 2014, 164, ⟨10.1016/j.dam.2012.02.016⟩
Accès au bibtex
https://arxiv.org/pdf/1309.2749 BibTex
titre
Detecting wheels
auteur
Emilie Diot, Sébastien Tavenas, Nicolas Trotignon
article
Applicable Analysis and Discrete Mathematics, 2014, 8 (1), ⟨10.2298/AADM131128023D⟩
Accès au bibtex
https://arxiv.org/pdf/1308.6433 BibTex
titre
Fast recognition of doubled graphs
auteur
Frédéric Maffray
article
Theoretical Computer Science, 2014, 516, pp.96-100. ⟨10.1016/j.tcs.2013.11.020⟩
Accès au bibtex
BibTex